1. Field of the Invention
The invention relates in general to the field of digital systems and, more particularly, to buses used with digital systems. Specifically, the invention relates to a bus protocol for preventing a specific type of node from becoming a bus arbitration controller.
2. Description of the Related Art
FIG. 1 illustrates a bus 100 to which a processor 105, digital camera 110, monitor 115, and mouse 120 are connected. Digital signals may be applied to the bus 100 and routed to any of the previously mentioned devices. If the digital camera 110 needs to send a signal to the monitor 115, the digital camera 110 has to gain access to the bus 100. Generally, one of the devices attached to the bus 100 is designated as the bus arbitration controller and controls when signals are applied to the bus 100. In this example, the processor 105 has been designated as the bus arbitration controller.
For the digital camera 110 to gain access to the bus 100, the digital camera 110 must send a bus control request to the processor 105. The bus control request essentially involves "asking" permission to be the device that applies a signal to the bus 100. One skilled in the art will appreciate that a signal applied to the bus may be a packet of digital information (e.g., data). The processor 105 decides if access will be granted to the digital camera 110. Arbitration of the bus 100 becomes necessary in order to minimize the likelihood of simultaneous or overlapping signals being applied to the bus 100.
Assuming that the processor 105, as the bus arbitration controller, allows the digital camera 110 access to the bus 100, the digital camera 110 will send a header along with the signal to indicate the signal is for the monitor 115. When the monitor 115 receives the signal, it will respond quickly by sending an acknowledgment to the digital camera 110. The digital camera 110 would accept the acknowledgment, and that would be the end of the digital camera's cycle as the bus master.
FIG. 2 illustrates a more detailed view of the four previously mentioned devices that are connected to the bus 100. Each of the devices has a link logic circuit 200 and a physical logic circuit 205. The physical logic circuit 205 receives the bus signals from the link logic circuit 200 and provides switching signals to be applied to the bus 100. A node is generally defined as having both a physical and link logic circuit and at least one associated device (e.g., the processor 105).
For a device to be designated as the bus arbitration controller, the nodes associated with each device generally have some structure. The structuring of a bus is generally referred to as bus configuration in the art. The bus configuration process includes identifying all of the nodes connected to the bus, which is often initiated when devices are added/removed from the bus. When the nodes have been connected, a bus "tree" is formed, after which the nodes on the bus are numbered. Finally, bus arbitration is controlled by the designated node.
The nodal "trees" generally consist of multiple branches and a root. The node at the top of the tree is often designated as the root node, and the device associated with that node is designated as the bus arbitration controller. All of the branches of the nodal tree have at least one connection to the root node and do not form a loop. One skilled in the art will appreciate that for a nodal tree to be formed, there has to be a "tree" identification process in which the relationship of the nodes are decided and the root node is designated.
FIG. 3A illustrates six nodes 310-324 that are associated with five devices (not shown). All of the nodes in FIG. 3A are connected to only one other node except nodes 310 and 320. Since the nodes 310 and 320 are connected to multiple nodes, the remaining nodes 312, 314, 322, 324 immediately initiate the tree identification process by sending parent-notify requests to the only other node to which they are connected. For example, the nodes 312, 314 send parent-notify requests to node 310. The node 310 may agree to be the "parent" of the nodes 312, 314 and respond by sending child-notify responses to each of those nodes. A parent node is generally responsible for sending arbitration requests up toward the root node and sending access grants and denials down to its children nodes.
Simultaneously, the node 320 may send child-notify responses to the nodes 322, 324 after they have sent their individual parent-notify requests. When the nodes 310, 320 have accounted for all of their nodes except one, they send parent-notify requests to each other. Bus contention occurs when two nodes simultaneously send a parent-notify request to each other. The contention is generally resolved by having each of the nodes wait a randomly selected period of time. There are generally only two time periods that a node can wait, one of which is shorter than the other. After the nodes 310, 320 wait a selected period of time, they resend their parent-notify requests to each other.
If contention reoccurs, the nodes wait another randomly selected period of time. Otherwise, the first node to send the parent-notify request causes a child-notify response to be sent by the other node which is then designated as the root node. For example if the node 320 sends a parent-notify request before the node 310 sends a parent-notify request, the node 310 responds by sending a child-notify response to the node 320 and agrees to be the root node. In this example, FIG. 3B illustrates the tree configuration for the previous example cited. As shown, the node 320 has two child nodes, which are the nodes 322, 324. The node 310 has three child nodes corresponding to the nodes 320, 312, 314.
One skilled in the art will appreciate that if the node 324 wants to send some information to the node 314, it would first have to send a bus control request to the node 320, which forwards the request to the root node 310. If the root node 310 sends back a response granting the node 324 control of the bus, the node 324 sends the information to the node 320, who forwards it to the nodes 322, 310. The node 322 ignores the information since it does not have its identifier in the header, and the node 310 forwards the information to the nodes 312, 314. Similarly, the node 312 disregards the information, while the node 314 sends back an acknowledgment to indicate that the information has been received. The acknowledgment is sent to the node 310, which forwards it to the nodes 312, 320. The node 320 forwards the response to the nodes 322, 324. The node 324 receives the acknowledgment and relinquishes control of the bus. In the previous bus configuration process described, any node may become the root node.
For a node to be a root node, some additional logic features should be included in the physical logic circuit to provide effective arbitration of the bus. The root node may also need to have circuitry by which the passage of signals on the bus may be synchronized with some devices (e.g., a system clock). Since root nodes generally need additional logic, it becomes beneficial to have some of the less complex nodes connected to the bus whose physical logic circuit does not have all of the additional circuitry needed for root nodes. When these subphysical logic circuits are used to make subphysical (sub) nodes, the cost and time factors may be reduced. By allowing an undesirable node to become the root node, additional time is often spent by causing the bus to reset so a different node can become root.
Because the subphysical nodes contain less circuitry than the "regular" physical nodes, it would be best not to have a subphysical node become the root node. Thus, it would be beneficial to have a tree identification process that prevents subphysical nodes from becoming the bus arbitration controller.